import java.util.*;

/**
 * Created by qtbui on 2017/9/21.
 */
class Solution
{
    public int mySqrt(int x)
    {
        if(x==0 || x==1)
        {
            return x;
        }

        int left=1;
        int right=x;
        int mid=(1+x)/2;
        if(mid<0)
        {
            //int overflow
            mid=x/2;
        }

        while(true)
        {
            int result = (int)Math.pow(mid,2);
            if(result>x || mid>=46341)
            {
                //int overflow , sqrt(2147483647)=46340
                right=mid;
                mid=(left+right)/2;
                continue;
            }
            if(result==x)
            {
                return mid;
            }
            if(result<x)
            {
                if(Math.pow(mid+1,2)>x)
                {
                    return mid;
                }
                left=mid;
                mid=(left+right)/2;
            }
        }
    }
}

public class test
{
    public static void main(String[] args)
    {
        System.out.println(new Solution().mySqrt(999));
    }
}
